Factoring large integer numbers is a difficult mathematical problem. The problem of integer factorization can be formulated as: given a positive integer, find all the prime factors of the integer. Every positive integer has a unique prime factorization. For small numbers, such as 16, factoring is quite simple. However, as the number increases, in general, finding the factors becomes increasingly difficult. In fact, the problem becomes intractable on known computing devices for large numbers. Conversely, however, confirming that a set of primes is the prime factorization of a number is easy.
One particular set of integers that is interesting to factor are biprimes. Biprimes are integers that are the direct product of two, not necessarily distinct, prime factors. For example, 15 is a biprime since 3 and 5 are the only prime factors and it can be derived by multiplying them together. The factoring of biprimes is of interest in the fields of cryptography and cryptanalysis, among other fields. Some cryptography schemes use the difficulty of factoring large biprimes as the basis for their encryption system. For example, a large biprime is used to encrypt data such that decryption of the data is only possible through the identification of the prime factors of the biprime. Such an encryption scheme is not absolutely secure because it is possible to identify prime factors, albeit through considerable effort. Thus, security of data encrypted in such a manner is only ensured for the period of time that it would take a third party to identify the prime factors for the biprime used to encrypt the data. Thus, such encryption schemes are useful when the amount of time it would take an unauthorized third party to find the prime factors of the encryption is much longer than the amount of time the information would be useful.
Complexity Classes
Complexity theory is the quantitative study of the time it takes for a computer to solve a decision problem and the resources required to solve the decision problem. In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i.e., a true or false, or yes or no). These are also known as yes-or-no questions. Such problems are assigned to complexity classes, the number and type of which is ever changing, as new complexity classes are defined and existing ones merge through the contributions of computer scientists. One exemplary complexity class involves those decision problems that are solvable in polynomial time by a Turing machine (P, herein poly). Another exemplary complexity class involves those decision problems that are solvable in non-deterministic polynomial-time, or problems whose solution is verifiable in polynomial time (NP). Still another complexity class is NP-hard (non-deterministic polynomial-time hard; NPH), which includes decision problems that have been shown to be hard to solve. More specifically, NP-hard refers to the class of decision problems that contains all problems H such that for every decision problem L in NP there exists a polynomial-time many-one reduction to H, written L≦H. Informally, this class can be described as containing the decision problems that are at least as hard as any problem in NP. A decision problem is NP-Complete (NPC) if it is in NP and it is NP-hard.
A problem is equivalent, or harder to solve, than a known problem in NPC if there exists a polynomial time reduction to the instant problem from the known problem in NPC. Reduction can be regarded as a generalization of mapping. The mappings can be a one-to-one function, a many-to-one function, making use of an oracle, etc. The concept of complexity classes and how they define the intractability of certain decision problems is found in, for example, M. R. Garey, D. S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, ISBN: 0716710455, pp. 1-15.
It is not exactly known which complexity classes the integer factorization problem falls under. It is widely believed to be outside P, since there have been many attempts to find a polynomial-time solution but none have worked. It is also suspected to be outside NPC. The integer factorization problem, expressed as a decision problem, where it suffices to answer whether an integer N has a factor less than M, is a known NP problem. Also, the determination of whether an integer is prime, expressed as a decision problem, is a known P problem. In the field of quantum computing, Shor's algorithm for factoring numbers (discussed below) proved that factoring biprimes is in the bounded-error, quantum, polynomial (BQP) complexity class. This means it can be solved by a quantum computer in polynomial time with an error probability of at most 0.25 for all instances.
Quantum Computers
A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.
An analog processor is a processor that employs the fundamental properties of a physical system to find the solution to a computation problem. In contrast to a digital processor, which requires an algorithm for finding the solution followed by the execution of each step in the algorithm according to Boolean methods, analog processors do not involve Boolean methods.
A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).
In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers” International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.
There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer's qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms” arXiv.org:quant-ph/0005003 (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.
Another approach to quantum computation, called thermally-assisted adiabatic quantum computation, involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the system's Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, and quantum annealing, and are described, for example, in Farhi, E. et al., “Quantum Adiabatic Evolution Algorithms versus Simulated Annealing” arXiv:quant-ph/0201031 (2002), pp 1-16.
To test for primality (that is, whether a factor is prime), a classical algorithm may be used. For example, there are several known approximate primality algorithms, all of which run in polynomial time, which can determine without 100% certainty if a number is prime. There is also an exact classical algorithm that can determine primality with 100% certainty, and it is believed to run in polynomial time. The density of primes of length n is approximately nlog(n). Randomized polynomial time algorithms for determining if a number is prime include the Miller-Rabin primality test. Approximate primality tests include inverted Fermat's little theorem tests: if 2n−1=1 mod n then, with high probability, n is prime. Deterministic algorithms for determining primality include the Cohen-Lenstra test and the Agrawal-Kayal-Saxena test. The Agrawal-Kayal-Saxena test is exact and runs in O((log(n))12). See, for example, Cormen et al., 2001, Introduction to Algorithms, 2nd Edition, MIT Press, Cambridge, pp. 887-896; Cohen and Lenstra, 1984, “Primality testing and jacobi sums,” Mathematics of Computation 42(165), pp. 297-330; Agrawal et al., 2002, “PRIMES is in P,” manuscript available from the Indian Institute of Technology, http://www.cse.iitk.ac.in/inews/primality.html.
As mentioned previously, qubits can be used as fundamental units of information for a quantum computer. As with bits in UTMs, qubits can refer to at least two distinct quantities; a qubit can refer to the actual physical device in which information is stored, and it can also refer to the unit of information itself, abstracted away from its physical device.
Qubits generalize the concept of a classical digital bit. A classical information storage device can encode two discrete states, typically labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the classical information storage device, such as direction or magnitude of magnetic field, current or voltage, where the quantity encoding the bit state behaves according to the laws of classical physics. A qubit also contains two discrete physical states, which can also be labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the quantum information storage device, such as direction or magnitude of magnetic field, current or voltage, where the quantity encoding the bit state behaves according to the laws of quantum physics. If the physical quantity that stores these states behaves quantum mechanically, the device can additionally be placed in a superposition of 0 and 1. That is, the qubit can exist in both a “0” and “1” state at the same time, and so can perform a computation on both states simultaneously. In general, N qubits can be in a superposition of 2N states. Quantum algorithms make use of the superposition property to speed up some computations.
In standard notation, the basis states of a qubit are referred to as the |0 and |1 states. During quantum computation, the state of a qubit, in general, is a superposition of basis states so that the qubit has a nonzero probability of occupying the |0 basis state and a simultaneous nonzero probability of occupying the |1 basis state. Mathematically, a superposition of basis states means that the overall state of the qubit, which is denoted |Ψ, has the form |Ψ=a|0+b|1, where a and b are coefficients corresponding to the probabilities |a|2 and |b|2, respectively. The coefficients a and b each have real and imaginary components. The quantum nature of a qubit is largely derived from its ability to exist in a coherent superposition of basis states. A qubit will retain this ability to exist as a coherent superposition of basis states when the qubit is sufficiently isolated from sources of decoherence.
To complete a computation using a qubit, the state of the qubit is measured (i.e., read out). Typically, when a measurement of the qubit is performed, the quantum nature of the qubit is temporarily lost and the superposition of basis states collapses to either the |0 basis state or the |1 basis state and thus regains its similarity to a conventional bit. The actual state of the qubit after it has collapsed depends on the probabilities |a|2 and |b|2 immediately prior to the readout operation.
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach uses integrated circuits formed of superconducting materials, such as aluminum or niobium. The technologies and processes involved in designing and fabricating superconducting integrated circuits are similar to those used for conventional integrated circuits.
Superconducting qubits are a type of superconducting device that can be included in a superconducting integrated circuit. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices, as discussed in, for example Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. Charge devices store and manipulate information in the charge states of the device, where elementary charges consist of pairs of electrons called Cooper pairs. A Cooper pair has a charge of 2e and consists of two electrons bound together by, for example, a phonon interaction. See e.g., Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000), pp. 343-345. Flux devices store information in a variable related to the magnetic flux through some part of the device. Phase devices store information in a variable related to the difference is superconducting phase between two regions of the phase device. Recently, hybrid devices using two or more of charge, flux and phase degrees of freedom have been developed. See e.g., U.S. Pat. No. 6,838,694 and U.S. Pat. No. 7,335,909, where are hereby incorporated by reference in their entireties.
Classical Factoring Algorithms
There are many known classical algorithms that exist for computing the prime factorization of integers. These classical algorithms fall into two main categories: special-purpose algorithms and general purpose algorithms. The efficiency of special purpose algorithms is number dependent. That is, depending on the properties of the number, the time it takes for the special-purpose algorithm to find the factors greatly varies. If the algorithm gets “lucky” and gets a number that works well with it, the solution can be found fairly quickly. For some numbers, special purpose algorithms can fail to find a solution.
In contrast to special purpose algorithms, general purpose algorithms are almost guaranteed to work for any number. The run-time of general purpose algorithms depends solely on the size of the number being factored. For more information, see Lenstra, 2000, Designs, Codes, and Cryptography 19, 101-128.
Some examples of special purpose algorithms include Pollard's rho algorithm, William's p+1 algorithm, and Fermat's factorization method. Examples of general purpose algorithms include Dixon's algorithm, quadratic sieve, and general number field sieve. See Lenstra for more information about how factorization algorithms work. For very large numbers, general purpose algorithms are preferred. Currently, the largest RSA challenge biprime to be factored is a 200 digit number. The general number field sieve method was used to solve this number.
Known classical algorithms for prime factorization require substantial amounts of computational power. For example such problems typically require powerful computing architectures such as supercomputers, massively parallel computing systems, and distributed computing systems that operate over a network such as the Internet. Even with such powerful computing architectures, the run time of the algorithms is very long. For example, the 200 digit number took approximately 1.5 years to factor with a cluster of 80 computers operating at a clock speed of 2.2 GHz. For larger biprimes such as those used in encryption, which can be 300 digits or more, the calculation would require prohibitively large computational power and very long run times.
Quantum Factoring Algorithms
In 1994, Peter Shor developed an algorithm for factoring integers that is intended to be run on a quantum computer. Using the special properties of quantum computers, the algorithm is able to probabilistically factor in O((log N)3) time using O(log N) space, where space refers to the amount of computational memory needed and where N is the number to be factored. This polynomial run time was a significant improvement over the best classical algorithms, which ran in sub-exponential time. See Shor, 1997, SIAM J. Comput. 26, pp. 1484-1509. Recently, a group from IGM experimentally realized Shor's Algorithm by factoring the number fifteen using a rudimentary 7-qubit nuclear magnetic resonance (NMR) quantum computer. The group used circuit model quantum computing to implement their algorithm. See Vandersypen et al., 2001, Nature 414, 883. However, the Vandersypen et al. method utilized a priori knowledge of the answers. In addition, NMR computers, such as those used by Vandersypen et al. are not scalable, meaning that larger, more interesting numbers cannot be factored using the methods taught by Vandersypen et al.
A classical model of factoring, expressed as an optimization problem, is disclosed in Burges, 2002, Microsoft Technical Report MSR-TR-2002-83. That is, the method of Burges is different from other proposed algorithms because it attempts to map the prime factorization problem to an optimization problem rather than a decision problem. Optimization problems are a class of problems where the aim is the maximize or minimize one or more variables of the problem. In the case of Burges, the biprime and its factors are represented in bit form, with the factor bits being variables. Then, by using long multiplication of the factors to get the biprime, one can derive a set of factor equations. The factor equations are then reduced as much as possible and then cast into an optimization of coefficients in a single equation. The solution of the optimization problem should give the proper bit values of the factors, thus effectively factoring the biprime.
However, the drawback of the Burges algorithm is that it is limited to use on a classical computer. Optimization problems, though a different type of problem than prime factorization, can also take up a tremendous amount of computing power. Thus, the obstacle of sufficient resources still has not been solved.
Accordingly, there remains a need in the art for improved methods for prime factorization of large numbers.
Discrete Optimization
In mathematics and computer science, an optimization problem is one in which an optimal value of at least one parameter is sought. Typically, the parameter in question is defined by an objective function which comprises at least one variable. The optimal value of the parameter is then achieved by determining the value(s) of the at least one variable that maximize or minimize the objective function.
Discrete optimization is simply a special-case of optimization for which the variables used in the objective function are restricted to assume only discrete values. For example, the variables in the objective function may be restricted to all or a subset of the integers.
Constraint Satisfaction
The maximization or minimization of the objective function in an optimization problem (discrete or otherwise) is typically subject to a set of constraints, where a valid result may be required to satisfy all, or at least a subset, of the constraints. In some applications, simply finding a solution that satisfies all, or a subset, of the constraints may be all that is desired (i.e., there may be no additional objective function requiring maximization or minimization). Such problems are known as “constraint satisfaction problems” and may be viewed as a class of optimization problems in which the objective function is a measure of how well the constraints are (or are not) satisfied. Thus, throughout the remainder of this specification, the term “optimization problem” is used to encompass all forms of optimization problems, including constraint satisfaction problems.
Quadratic Unconstrained Binary Optimization Problems
A quadratic unconstrained binary optimization (“QUBO”) problem is a form of discrete optimization problem that involves finding a set of N binary variables {xi} that minimizes an objective function of the form:
      E    ⁡          (                        x          1                ,        …        ⁢                                  ,                  x          N                    )        =            ∑              i        ≤        j            N        ⁢                  Q        ij            ⁢              x        i            ⁢              x        j            where Q is typically a real-valued upper triangular matrix that is characteristic of the particular problem instance being studied. QUBO problems are known in the art and applications arise in many different fields, for example machine learning, pattern matching, economics and finance, and statistical mechanics, to name a few.Logic Circuits
For any problem that can be solved, a solution may be reached by following a prescribed set of steps. In many cases, the prescribed set of steps may be designed to include a set of logical steps called “logical operations.” Logical operations are the fundamental steps that are typically implemented in digital electronics and most classical computer algorithms.
For many computational problems, a sequence of steps that leads to a solution can be described by a logic circuit representation. A logic circuit representation includes at least one logical input that is transformed to at least one logical output through at least one logical operation. A logic circuit representation may include any number of logical operations arranged either in series or in parallel (or a combination of series and parallel operations), where each logical operation has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. Throughout this specification and the appended claims, the terms “intermediate logical input” and “intermediate logical output” are often used. Unless the specific context requires otherwise, the term “intermediate” here is intended to denote an input to/output from an individual logic gate which is an intermediate input/output with respect to the overall logic circuit. However, those of skill in the art will appreciate that a logical input to a logic circuit may correspond to an intermediate logical input to a particular logic gate, and similarly a logical output from a logic circuit may correspond to an intermediate logical output from a particular logic gate. For a first logical operation arranged in series with a second logical operation, at least one intermediate logical output from the first logical operation may correspond to at least one intermediate logical input to the second logical operation.
Each logical operation in a logic circuit is represented by a logic gate, for example, the NAND gate or the XOR gate, or a combination of logic gates. A logical operation may include any number of logic gates arranged either in series or in parallel (or a combination of series and parallel gates), where each logic gate has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. For a first logic gate arranged in series with a second logic gate, at least one intermediate logical output from the first logic gate may correspond to at least one intermediate logical input to the second logic gate. The complete logic circuit representation of a computational problem may include any number of intermediate logical operations which themselves may include any number of intermediate logic gates. Furthermore, the at least one logical input to the logic circuit representation may traverse any number of intermediate logical inputs and intermediate logical outputs in being transformed to the at least one logical output from the logic circuit representation. Unless the specific context requires otherwise, throughout the remainder of this specification and the appended claims the terms “logical input” and “logical output” are used to generally describe any inputs and outputs in a logic circuit representation, including intermediate inputs and outputs.
In some implementations, one or more logical inputs may produce a plurality of logical outputs. For example, if the circuit, an operation, or a gate produces an N-bit number as the result, then N logical outputs may be required to represent this number. Alternatively, one or more logical inputs may produce a single logical output. For example, if the circuit, an operation, or a gate produces TRUE or FALSE as the result, then only one logical output may be required to convey this information. A circuit that produces TRUE or FALSE as the result embodies “Boolean logic” and is sometimes referred to as a “Boolean circuit.” Boolean circuits are commonly used to represent NP-complete constraint satisfaction problems.
Quantum Processor
A computer processor may take the form of an analog processor, for instance a quantum processor such as a superconducting quantum processor. A superconducting quantum processor may include a number of qubits and associated local bias devices, for instance two or more superconducting qubits. Further detail and embodiments of exemplary quantum processors that may be used in conjunction with the present systems, methods, and apparatus are described in U.S. Pat. No. 7,533,068, US Patent Publication 2008-0176750, US Patent Publication 2009-0121215, and PCT Patent Publication 2009-120638.
Adiabatic Quantum Computation
Adiabatic quantum computation typically involves evolving a system from a known initial Hamiltonian (the Hamiltonian being an operator whose eigenvalues are the allowed energies of the system) to a final Hamiltonian by gradually changing the Hamiltonian. A simple example of an adiabatic evolution is:He=(1−s)Hi+sHf 
where Hi is the initial Hamiltonian, Hf is the final Hamiltonian, He is the evolution or instantaneous Hamiltonian, and s is an evolution coefficient which controls the rate of evolution. As the system evolves, the coefficient s goes from 0 to 1 such that at the beginning (i.e., s=0) the evolution Hamiltonian He is equal to the initial Hamiltonian Hi and at the end (i.e., s=1) the evolution Hamiltonian He is equal to the final Hamiltonian Hf. Before the evolution begins, the system is typically initialized in a ground state of the initial Hamiltonian Hi and the goal is to evolve the system in such a way that the system ends up in a ground state of the final Hamiltonian Hf at the end of the evolution. If the evolution is too fast, then the system can be excited to a higher energy state, such as the first excited state. In the present systems, methods, and apparatus, an “adiabatic” evolution is considered to be an evolution that satisfies the adiabatic condition:{dot over (s)}|1|dHe/ds|0|=δg2(s)where {dot over (s)} is the time derivative of s, g(s) is the difference in energy between the ground state and first excited state of the system (also referred to herein as the “gap size”) as a function of s, and δ is a coefficient much less than 1.
The evolution process in adiabatic quantum computing may sometimes be referred to as annealing. The rate that s changes, sometimes referred to as an evolution or annealing schedule, is normally slow enough that the system is always in the instantaneous ground state of the evolution Hamiltonian during the evolution, and transitions at anti-crossings (i.e., when the gap size is smallest) are avoided. Further details on adiabatic quantum computing systems, methods, and apparatus are described in U.S. Pat. No. 7,135,701.
Quantum Annealing
Quantum annealing is a computation method that may be used to find a low-energy state, typically preferably the ground state, of a system. Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend towards lower energy states because lower energy states are more stable. However, while classical annealing uses classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing may use quantum effects, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly. It is known that the solution to a hard problem, such as a combinatorial optimization problem, may be encoded in the ground state of a system Hamiltonian and therefore quantum annealing may be used to find the solution to such hard problems. Adiabatic quantum computation is a special case of quantum annealing for which the system, ideally, begins and remains in its ground state throughout an adiabatic evolution. Thus, those of skill in the art will appreciate that quantum annealing systems and methods may generally be implemented on an adiabatic quantum computer, and vice versa. Throughout this specification and the appended claims, any reference to quantum annealing is intended to encompass adiabatic quantum computation unless the context requires otherwise.
Quantum annealing is an algorithm that uses quantum mechanics as a source of disorder during the annealing process. The optimization problem is encoded in a Hamiltonian HP, and the algorithm introduces strong quantum fluctuations by adding a disordering Hamiltonian HD that does not commute with HP. An example case is:HE=HP+ΓHD.
where Γ changes from a large value to substantially zero during the evolution and HE may be thought of as an evolution Hamiltonian similar to He described in the context of adiabatic quantum computation above. The disorder is slowly removed by removing HD (i.e., reducing Γ). Thus, quantum annealing is similar to adiabatic quantum computation in that the system starts with an initial Hamiltonian and evolves through an evolution Hamiltonian to a final “problem” Hamiltonian HP whose ground state encodes a solution to the problem. If the evolution is slow enough, the system will typically settle in a local minimum close to the exact solution; the slower the evolution, the better the solution that will be achieved. The performance of the computation may be assessed via the residual energy (distance from exact solution using the objective function) versus evolution time. The computation time is the time required to generate a residual energy below some acceptable threshold value. In quantum annealing, HP may encode an optimization problem and therefore HP may be diagonal in the subspace of the qubits that encode the solution, but the system does not necessarily stay in the ground state at all times. The energy landscape of HP may be crafted so that its global minimum is the answer to the problem to be solved, and low-lying local minima are good approximations.
The gradual reduction of Γ in quantum annealing may follow a defined schedule known as an annealing schedule. Unlike traditional forms of adiabatic quantum computation where the system begins and remains in its ground state throughout the evolution, in quantum annealing the system may not remain in its ground state throughout the entire annealing schedule. As such, quantum annealing may be implemented as a heuristic technique, where low-energy states with energy near that of the ground state may provide approximate solutions to the problem.
In the figures, identical reference numbers identify similar elements or acts. The sizes and relative positions of elements in the figures are not necessarily drawn to scale. For example, the shapes of various elements and angles are not drawn to scale, and some of these elements are arbitrarily enlarged and positioned to improve legibility. Further, the particular shapes of the elements as drawn are not intended to convey any information regarding the actual shape of the particular elements and have been solely selected for ease of recognition in the figures. Furthermore, while the figures may show specific layouts, one skilled in the art will appreciate that variations in design, layout, and fabrication are possible and the shown layouts are not to be construed as limiting the layout of the present systems, methods and apparatus.